package org.hw.algorithm.LinkedList;

public class LinkedFactory {

    /*单链表逆序-临时三节点后移操作*/
    public static LinkNode reverseLinkTemp3(LinkNode head) {
        if (head == null) return head;
        LinkNode p1 = head;
        LinkNode p2 = head.next;
        LinkNode p3 = null;
        while (p2 != null) {
            p3 = p2.next;
            p2.next = p1;
            p1 = p2;
            p2 = p3;
        }
        // 原链表头结点现在成为了尾结点，所以尾结点的next设置为null，防止形成循环链表：head.next=null
        head.next = null;
        return p1;
    }

    /**
     * 单链表逆序-递归实现 （1）
     * 为了方便理解，假设链表只有两个元素，那么情况如下：
     * 1.栈底的元素为 node.next ,栈顶的元素为 node
     * 2.将两个节点逆序，栈底 -> 栈顶 : [node.next].next=node;注意设置[node].next=null，防止形成循环链表;
     * 3.递归的终止条件是 node.next==null，到达栈底，将栈底元素一层层返回。
     *
     * @param node
     * @return
     */
    public static LinkNode reverseLinkRecurve(LinkNode node) {
        //终止条件
        if (node == null || node.next == null) {
            return node;
        }
        LinkNode tmp = reverseLinkRecurve(node.next);
        //head.next是当前节点，head是上一个节点。让当前节点的next指向上一个节点。并将上一个节点next置空。
        node.next.next = node;
        // 上层节点的next置 null，防止形成循环
        node.next = null;
        return tmp;
    }

    /**
     * 单链表逆序-递归实现 （2）
     *
     * @param head
     * @return
     */
    public LinkNode reverseList(LinkNode head) {
        return recur(null, head);    // 调用递归并返回
    }

    private LinkNode recur(LinkNode pre, LinkNode cur) {
        if (cur == null) return pre; // 终止条件
        LinkNode res = recur(cur, cur.next);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }

    /**
     * 链表逆序-递归实现
     *
     * @param head     链表
     * @param haveHead 是否头结点
     * @return
     * @author hewei
     * @date 2021/3/22
     */
    public static LinkNode reverseLinkRecurve(LinkNode head, boolean haveHead) {

        if (haveHead) {
            if (head == null || head.next == null) {
                return head;
            }
            LinkNode newHead = reverseLinkRecurve(head.next, haveHead);
            head.next.next = head;
            head.next = null;
            return newHead;
        } else {
            if (head == null) {
                return head;
            }
            LinkNode newHead = reverseLinkRecurve(head.next, !haveHead);
            head.next = newHead;
            return newHead;
        }
    }

    /**
     * 单链表逆序-引入临时节点实现
     *
     * @param head
     * @return
     */
    public static LinkNode reverseLinkTemp(LinkNode head) {
        if (head == null) {
            return head;
        }
        LinkNode temp = new LinkNode();
        temp.next = head;
        LinkNode prev = temp.next;
        LinkNode pcur = prev.next;
        while (pcur != null) {
            prev.next = pcur.next;
            pcur.next = temp.next;
            temp.next = pcur;
            pcur = prev.next;
        }
        return temp.next;
    }

    /*单链表逆序-*/
    public LinkNode reverseLink(LinkNode head) {
        LinkNode next;
        LinkNode prev = null;
        while (head != null) {
            next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    /**
     * 链表求和
     * 9->2->3 329
     * 4->5->6 654
     * 3->8->9 983
     * sum:329+654=983
     * 两个链表每个节点分别表示两个数字的每一位数，数字是从头节点开始逆序存放求两个数组的和
     */
    public static LinkNode linkNumberSum(LinkNode l1, LinkNode l2) {
        int carry = 0;
        LinkNode newHead = new LinkNode();
        LinkNode temp = newHead;
        while (l1 != null || l2 != null) {
            int num1 = l1 != null ? l1.value : 0;
            int num2 = l2 != null ? l2.value : 0;
            int sum = carry + num1 + num2;
            /*计算进位*/
            carry = sum / 10;
            /*计算当前位*/
            temp.next = new LinkNode(sum % 10);
            temp = temp.next;

            l1 = l1.next;
            l2 = l2.next;
        }
        if (carry > 0) temp.next = new LinkNode(carry);
        return newHead.next;
    }

    /**
     * 返回链表中倒数第k个元素
     * 两个指针节点
     * temp 遍历链表节点
     * target 获取目标节点
     * 假设链表长度为 L，则 倒数第 k 个节点 也就是顺序 第 L-k+1 个节点。
     * 让 temp 指针节点先往后遍历 k 个节点，在 第 k 个节点时 target 开始从链表头遍历，两个指针同步遍历
     * 直到 temp 节点遍历到链表尾部，这是target 节点就是倒数第 k 个节点。
     */

    public static LinkNode getEndNode(LinkNode head, int k) {
        if (head == null || k < 0) return null;
        int index = 0;
        LinkNode temp = head;
        LinkNode target = head;
        while (temp.next != null) {
            index++;
            k--;
            /*temp遍历了到第k个节点时 target 开始从头遍历*/
            if (k <= 0) {
                target = target.next;
            }
            temp = temp.next;
        }
        // 如果节点个数小于所求的倒数第k个节点，则返回空
        if (index < k) return null;
        return target;
    }

    /**
     * 两个链表的交点
     * 双指针法，形成环形访问，一定会在交点处相遇或者都为null
     * */
    public static LinkNode crossNode(LinkNode headA, LinkNode headB) {
        // 任一链表为空，不肯能相交
        if (headA==null || headB==null) return null;
        LinkNode pA=headA,pB=headB;
        while (pA != pB) {
            // pA 为 null 时，指向链表B的头结点
            pA = (pA == null) ? headB : pA.next;
            // pB 为 null 时，指向链表A的头结点
            pB = (pB == null) ? headA : pB.next;
        }
        //返回交点或者null
        return pA;
    }

    /**
     * 单链表是否有环
     * 快慢指针法
     * 1. 从头结点开始，慢指针一次后移一步，快指针一次后移两步
     * 2. 直到两个指针相等表示有环
     * */
    public static boolean hasCycle(LinkNode head) {
        if ( head == null || head.next==null) return false;
        LinkNode fast = head, slow = head;
        while (fast != null && slow != null) {
            slow=slow.next;
            fast=fast.next.next;
            if (fast==slow) return true;
        }
        return false;
    }


}
